<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta name="description" content="">
    <meta name="that js dude" content="">    
    <title>JS: Graph related questions -3</title>

    <link rel="shortcut icon" href="images/favicon.jpg">    
    <link rel="stylesheet" href="css/bootstrap.min.css" >
    <link rel="stylesheet" href="css/zenburn.css">
    <!-- Custom styles for this template -->
    <link rel="stylesheet" href="css/stite.css">

    <!-- Just for debugging purposes. Don't actually copy this line! -->
    <!--[if lt IE 9]><script src="docs-assets/js/ie8-responsive-file-warning.js"></script><![endif]-->

    <!-- HTML5 shim and Respond.js IE8 support of HTML5 elements and media queries -->
    <!--[if lt IE 9]>
      <script src="https://oss.maxcdn.com/libs/html5shiv/3.7.0/html5shiv.js"></script>
      <script src="https://oss.maxcdn.com/libs/respond.js/1.3.0/respond.min.js"></script>
    <![endif]-->
  </head>

  <body>

    <!-- Main jumbotron for a primary marketing message or call to action -->
    <div class="jumbotron">
      <div class="container">
        <h1>JS: Graph related questions</h1>
        <h4>Graph relatd interview questions for expert JavaScript developers</h4>
        <h2>part-8: expert</h2>
        <p>June 29, 2014</p>
        <!-- <div id="fb-root"></div><div class="fb-like" data-href="http://www.thatjsdude.com/interview/dom.html" data-layout="button_count" data-action="like" data-show-faces="false" data-share="false"></div><div class="g-plusone"></div>  -->
      </div>
    </div>
    <div class="container container-fluid">
      <!-- Example row of columns -->

      <div class="row center">
        <!-- <iframe width="853" height="480" src="//www.youtube.com/embed/Rx_JFOSxgpY" frameborder="0" allowfullscreen></iframe> -->
      </div>

      <!-- <p class="gray">if you are little more comfortable or claim to be comfortable with javascript, these questions would not be enough for you. more coming</p>
      <p class="gray"> <span class="purpleBold">More Questions</span> <a href="css.html">css interview questions</a>, <a href="html.html">html interview questions</a> </p> -->
      <div id="questionList">
        <h2>todo list</h2>
        <h4>graph</h4>
        <ul>
          <li><a href="https://www.quora.com/What-graph-topics-should-I-study-in-order-to-be-adequately-prepared-for-a-Google-Software-Engineer-interview">very good: Graph question in Quora</a></li>
          <li>All categories and pages in wikipedia related to<a href="http://en.wikipedia.org/wiki/Category:Graph_algorithms">Graph Theory</a></li>
          <li><a href="http://en.wikipedia.org/wiki/Directed_graph">directed graph</a></li>
          <li><a href="http://en.wikipedia.org/wiki/Weighted_graph#Weighted_graphs_and_networks">weighted graphs and networks</a></li>
          <li><a href="http://en.wikipedia.org/wiki/Shortest_path">shortest path</a></li>
          <li><a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm">dijkstra algorithm</a></li>
          <li><a href="http://en.wikipedia.org/wiki/Maximal_flow">maximum flow problem</a></li>
          <li><a href="http://en.wikipedia.org/wiki/Graph_colouring">graph coloring</a></li>
          <li><a href="http://en.wikipedia.org/wiki/Travelling_salesman_problem">Traveling sales man problem</a></li>
          <li><a href="http://en.wikipedia.org/wiki/A*_search_algorithm">A* Algorithm</a></li>
          <li><a href="http://en.wikipedia.org/wiki/B*">B* Algorithm</a></li>
          <li><a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm">Dijkstra Algorithm</a></li>
        </ul>
        <h4>From geek for geeks</h4>
        <ul>
          <li><a href=""></a></li>
          <li><a href="http://www.geeksforgeeks.org/find-edge-disjoint-paths-two-vertices/">maximum number of edges between two disjoint vertices</a></li>
          
          <li><a href="http://www.geeksforgeeks.org/connectivity-in-a-directed-graph/">connectivity-in-a-directed-graph</a></li>
          <li><a href=""></a></li>
          <li><a href="http://www.geeksforgeeks.org/shortest-path-exactly-k-edges-directed-weighted-graph/">Shortest path exactly k paths</a></li>
          <li><a href="http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/">shortest path in a directed acyclic path</a></li>
          <li><a href="http://www.geeksforgeeks.org/count-possible-paths-source-destination-exactly-k-edges/">all possible path with k steps</a></li>
          <li><a href="http://www.geeksforgeeks.org/interesting-shortest-path-questions-set-1/">Interesting questions related to shortest path</a></li>
          <li><a href="http://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/">Tarjan algorithm</a></li>
          <li><a href="http://www.geeksforgeeks.org/euler-circuit-directed-graph/">Euler circuit</a></li>
          <li><a href="http://www.geeksforgeeks.org/bridge-in-a-graph/">bridge in a graph</a></li>
          <li><a href="http://www.geeksforgeeks.org/find-if-there-is-a-path-between-two-vertices-in-a-given-graph/">check if path exists between two paths</a></li>
          <li><a href="http://www.geeksforgeeks.org/bipartite-graph/">bipartite graph</a></li>
          <li><a href="http://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/">Ford Fulkerson algorithm</a></li>
          <li><a href="http://www.geeksforgeeks.org/the-celebrity-problem/">celebrity problem</a></li>
          <li><a href="http://www.geeksforgeeks.org/fleurys-algorithm-for-printing-eulerian-path/">printing Eulerian path by Fleury's Algorithm</a></li>
          <li><a href="http://www.geeksforgeeks.org/johnsons-algorithm/">Jhonson algorithm</a></li>
          <li><a href="http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/">Greedy Algorithm</a></li>
        </ul>
        <h4>coloring</h4>
        <ul>
          <li><a href="http://www.geeksforgeeks.org/graph-coloring-applications/">graph coloring</a></li>
          <li><a href="http://www.geeksforgeeks.org/graph-coloring-set-2-greedy-algorithm/">graph coloring (greedy algorith)</a></li>
          <li><a href=""></a></li>
        </ul>
      </div>
      <div id="graph">
        <h2>Graph</h2>
        <p><strong>Question:</strong> How do you write a graph in JS?</p>
        <p><strong>Answer:</strong></p>
        <pre><code>
function Graph(){
   this._nodes={};
   this.nodeSize = 0;
   this.edgeSize = 0;
}
        </code></pre>
        <p><strong>Add node: </strong> Use simple number or string as key of the node. After creating a node, a simple node is created and returned. If needed you can add new properties.</p>
        <pre><code>
Graph.prototype.addNode = function(id){
   if(!this._nodes[id]){
      this.nodeSize++;
      return this._nodes[id] = {
         _outEdges:{},
         _inEdges:{}
      }
   }
}
        </code></pre>
        <p><strong>Add Edge:</strong></p>
        <pre><code>
Graph.prototype.addEdge = function (fromId, toId, weight){
   var fromNode, toNode, edge;
   

  if(this.getEdge(fromId, toId)){
    return;
  }
  
  fromNode = this._nodes[fromId];
  toNode = this._nodes[toId];

  if(!fromNode || !toNode){
    return;
  }

  edge = {weight: weight |1};

  fromNode._outEdges[toId] = edge;
  toNode._inEdges[fromId] = edge;

  this.edgeSize++;

  return edge;
}
        </code></pre>
        <p><strong>Get Edge:</strong></p>
        <pre><code>
Graph.prototype.getEdge = function(fromId, toId){
  var fromNode = this._nodes[fromId];
  var toNode = this._nodes[toId];

  if(fromNode && toNode){
     return fromNode._outEdges[toId];
  }
}
        </code></pre>
        <h3>Graph Utility Function</h3>
        <p><strong>forEachNode</strong></p>
        <pre><code>
Graph.prototype.forEachNode = function(fn){
   var node, nodeId, allNodes;
   allNodes = this._nodes;
  
   for(nodeId in allNodes){
     if(allNodes.hasOwnProperty(nodeId)){
        fn(allNodes[nodeId], nodeId);
    }
  }
}
        </code></pre>
        <p><strong>forEachEdge</strong></p>
        <pre><code>
Graph.prototype.forEachEdge = function(fn){
  var edge,node, nodeId, toId, allNodes, outEdges;

  allNodes = this._nodes;

  for(nodeId in allNodes){
    if(!allNodes.hasOwnProperty(nodeId)) continue;
    
    node = allNodes[nodeId];

    outEdges = node._outEdges;

    for(toId in outEdges){
      if(!outEdges.hasOwnProperty(toId)) continue;

      fn(outEdges[toId], nodeId + ' to ' +toId);
    }
  }
}
        </code></pre>
        <p>ref: <a href="https://github.com/chenglou/data-structures/blob/master/distribution/Graph.js">javascript code for graph</a></p>
      </div>
      <div id="dfs">
        <h2>Depth First Search</h2>
        <p><strong>Question:</strong> Write an algorithm for Depth First Search in a Graph</p>
        <p><strong>Answer:</strong></p>
        <p>Be careful, graph could have cycle (pointing to itself)</p>
        <pre><code>
dfs(vertex v)
{
visit(v);
for each neighbor w of v
    if w is unvisited
    {
    dfs(w);
    add edge vw to tree T
    }
}
        </code></pre>
        <p>ref:  <a href="http://www.ics.uci.edu/~eppstein/161/960215.html">dfs and bfs pseudocode</a></p>
      </div>
      <div id="bfs">
        <h2>Breadth First Search</h2>
        <p><strong>Question:</strong> Write an algorithm for Breadth First Search</p>
        <p><strong>Answer:</strong></p>
      </div>
      <div>
        <h2>Questions list</h2>
        <h4>from cracking the coding interview</h4>
        <ul>
          <li>fore directed graph, check whether there is a route between two node</li>
          <li><a href="http://www.crazyforcode.com/tree/">carzy for code list of tree questions</a></li>
          <li><a href="http://www.geeksforgeeks.org/forums/forum/trees-specific-questions/">geeks for geeks questions</a></li>
          <li><a href="http://www.glassdoor.com/Interview/binary-trees-interview-questions-SRCH_KT0,12.htm">glassdoor questions</a></li>
          <li><a href="https://www.youtube.com/playlist?list=PLC3855D81E15BC990">you tube got some questions as well</a></li>
          <li><a href="http://www.careercup.com/page?pid=trees-and-graphs-interview-questions">career cup list of question</a></li>
        </ul>
      </div>
      <div>
        <h2>References</h2>
        <li><a href="http://www.cs.usfca.edu/~galles/visualization/Algorithms.html">Data Structre Visualization</a></li>
      </div>
      <div>
        <h3 class="purpleBold">Express anger!</h3>
        <!-- <p class="gray">Feel free to express your anger (sorry folks, you have to use g+.). Also point out my mistakes ( technical, wrong answer, spelling, grammar, sentence..., whatever), let your dude learn and grow.</p>
        <script src="https://apis.google.com/js/plusone.js"></script>
        <div class="g-comments"
            data-href="http://www.thatjsdude.com/interview/dom.html"
            data-width="642"
            data-first_party_property="BLOGGER"
            data-view_type="FILTERED_POSTMOD">
        </div>         -->
      </div>
      <hr>

      <footer>
        <p>&copy;thatJSDude 2014</p>
      </footer>
    </div> <!-- /container -->


    <!-- Bootstrap core JavaScript
    ================================================== -->
    <!-- Placed at the end of the document so the pages load faster -->
    <script src="js/jquery-2.0.3.min.js"></script>    
    <script src="js/bootstrap.min.js"></script>
    <script src="js/highlight.pack.js"></script>    
    <script>hljs.initHighlightingOnLoad();</script>
    <script src="js/toggleExample.js"></script>
    <script type="text/javascript">
      //social plugins
      // //g+
      // (function() {
      //   var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true;
      //   po.src = 'https://apis.google.com/js/platform.js';
      //   var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s);
      // })();
      // //fb
      // (function(d, s, id) {
      //   var js, fjs = d.getElementsByTagName(s)[0];
      //   if (d.getElementById(id)) return;
      //   js = d.createElement(s); js.id = id;
      //   js.src = "//connect.facebook.net/en_US/all.js#xfbml=1";
      //   fjs.parentNode.insertBefore(js, fjs);
      // }(document, 'script', 'facebook-jssdk'));
    </script>
    <script type="text/javascript">        
        document.getElementById('listToDestroy').addEventListener('click', function (e) {
          var elm = e.target.parentNode;
          elm.parentNode.removeChild(elm);
          e.preventDefault();
        }); 

        document.getElementById('doubleHolder').addEventListener('click', function (e) {
   
           if(e.target.classList.contains('double')){
              var btn = document.createElement('button');
              btn.setAttribute('class', 'double');
              btn.innerHTML = 'double';

              var btn2 = document.createElement('button');
              btn2.setAttribute('class', 'double');
              btn2.innerHTML = 'double';
             
              this.appendChild(btn);
              this.appendChild(btn2);
              this.removeChild(e.target);   
           }
        }); 
    </script>
  </body>
</html>
